package Aufgabe1_gleichwertige_loesungen;

import java.util.*;
import static Aufgabe1_gleichwertige_loesungen.FileOperations.*;

public class Teilsumme {
    public static int maxteilsumme3(List<Integer> folge){
        long start_zeit = System.currentTimeMillis();
        // Kleinster Integerwert wegen minus bereich
        int teilsumme_max = Integer.MIN_VALUE;
        int index_von = 0;
        int index_bis = 0;
        int folge_size = folge.size();
        long zugriffe=0;
        
        for(int i=0;i<folge_size;i++){


            for(int j=i;j<folge_size;j++){
                int temp=0;                 //aktuelle teilsumme

                for(int k=i;k<=j;k++){      //adition aller teilfolgeglieder
                    temp+=folge.get(k);
                    zugriffe++;
                }
                if(temp>teilsumme_max){
                    teilsumme_max=temp;
                    index_von=i;
                    index_bis=j;
                }
            }
        }
        long end_zeit = System.currentTimeMillis();
        long laufzeit = end_zeit-start_zeit;
        System.out.println("maxteilsumme3 :");
        System.out.println("Gebrauchte Zeit in ms"+laufzeit);
        System.out.println("Zugriffe auf Folge:"+zugriffe);
        
        writeMessdaten(new ArrayList(Arrays.asList(new Object[]{folge.size(),"maxteilsumme3",teilsumme_max,index_von,index_bis,laufzeit,"N/A",zugriffe})));
        return teilsumme_max;
    }
    
    public static int maxteilsumme2(List<Integer> folge){
        long start_zeit = System.currentTimeMillis();
        int teilsumme_max = Integer.MIN_VALUE;
        int index_von = 0;
        int index_bis = 0;
        int folge_size = folge.size();
        long zugriffe=0;
        long mzugriffe=0;
        //matrix initialisieren
        ArrayList<ArrayList<Integer>> matrix = new ArrayList(folge_size);
        for(int i=0;i<folge_size;i++){
            matrix.add(new ArrayList<Integer>(folge_size-i));
        }
        //berechnung aller teilsummen und speicherung in der matrix
        for(int i=0;i<folge_size;i++){
            matrix.get(i).add(folge.get(i));    //ersten wert von j eintragen
            zugriffe++;
            for(int j=1;j<folge_size-i;j++){
                matrix.get(i).add(matrix.get(i).get(j-1)+folge.get(i+j));
                zugriffe++;
                mzugriffe++;
            }
        }
        //finden der groesstn teilsumme
        for(int i=0;i<folge_size;i++){
            for(int j=0;j<folge_size-i;j++){
                int tmp = matrix.get(i).get(j);
                mzugriffe++;
                if(tmp>teilsumme_max){
                    teilsumme_max=tmp;
                    index_von=i;
                    index_bis=i+j;
                }
            }
        }
        long end_zeit = System.currentTimeMillis();
        long laufzeit = end_zeit-start_zeit;
        System.out.println("maxteilsumme2 :");
        System.out.println("Gebrauchte Zeit in ms"+laufzeit);
        System.out.println("Zugriffe auf Folge:"+zugriffe);       
        System.out.println("Zugriffe auf Matrix:"+mzugriffe);
        System.out.println("Zugriffe kombiniert:"+(zugriffe+mzugriffe));
        writeMessdaten(new ArrayList(Arrays.asList(new Object[]{folge.size(),"maxteilsumme2",teilsumme_max,index_von,index_bis,laufzeit,"N/A",zugriffe})));
        return teilsumme_max;
    }
    
    public static int[] rechtesRandMax(List<Integer> folge, int links, int rechts){
        int rand_max = Integer.MIN_VALUE;
        int indexI=rechts;
        int sum=0;
        for(int i=rechts;i>=links;i--){
            sum+=folge.get(i);
            rek_zugriffe++;
            if(sum>rand_max){
                rand_max=sum;
                indexI=i;
            }
        }
        int[] res ={rand_max,indexI};
        return res;
    }
      public static int[] linkesRandMax(List<Integer> folge, int links, int rechts){
        int rand_max = Integer.MIN_VALUE;
        int indexJ=links;
        int sum=0;
        for(int i=links;i<=rechts;i++){
            sum+=folge.get(i);
            rek_zugriffe++;
            if(sum>rand_max){
                rand_max=sum;
                indexJ=i;
            }
        }
        int[] res ={rand_max,indexJ};
        return res;
    }
    public static long rek_zugriffe=0;
    public static final int INDEX_ANFANG = 1;
    public static final int INDEX_ENDE = 2;
    public static final int TEILSUMME_RUECKGABE = 0;
    public static final int INDEX_RUECKGABE = 1;
    
    public static int maxteilsummeRekursiv(List<Integer> folge){
        long start_zeit = System.currentTimeMillis();
        int[] result = maxteilsummeRekursiv(folge,0,folge.size()-1);
        
        long end_zeit = System.currentTimeMillis();
        long laufzeit = end_zeit-start_zeit;
        System.out.println("maxteilsummeRekursiv :");
        System.out.println("Zugriffe auf Folge:"+rek_zugriffe);    
        System.out.println("Gebrauchte Zeit in ms"+(laufzeit));
        writeMessdaten(new ArrayList(Arrays.asList(new Object[]{folge.size(),"maxteilsummeRekursiv",result[0],result[1],result[2],laufzeit,"N/A",rek_zugriffe})));
        return result[0];
        
    }
    public static int[] maxteilsummeRekursiv(List<Integer> folge,int links, int rechts){
        int index_von=0;
        int index_bis=0;
        int teilsumme_max=0;
        if (links == rechts){
                        rek_zugriffe++;
			teilsumme_max = Math.max(0, folge.get(links));
                        index_von=links;
                        index_bis=rechts;
                        }
		else {
			final int mitte = (rechts + links)/2;
			final int[] maxLinks = maxteilsummeRekursiv(folge, links, mitte);
			final int[] maxRechts = maxteilsummeRekursiv(folge, mitte+1, rechts);
			final int[] rechtesRandMax = rechtesRandMax(folge, links, mitte);
				// linke Hälfte
			final int[] linkesRandMax = linkesRandMax(folge, mitte+1, rechts);
				// rechte Hälfte
			//return Math.max(maxRechts, Math.max(maxLinks, rechtesRandMax+linkesRandMax));
                        
                        //groesste teilsumme bestimmen
                        if(maxLinks[0]>teilsumme_max){
                            teilsumme_max=maxLinks[TEILSUMME_RUECKGABE];
                            index_von=maxLinks[INDEX_ANFANG];
                            index_bis=maxLinks[INDEX_ENDE];
                        }
                        if(maxRechts[0]>teilsumme_max){
                            teilsumme_max=maxRechts[TEILSUMME_RUECKGABE];
                            index_von=maxRechts[INDEX_ANFANG];
                            index_bis=maxRechts[INDEX_ENDE];
                        }
                        if(rechtesRandMax[0]+linkesRandMax[0]>teilsumme_max){
                            teilsumme_max=rechtesRandMax[TEILSUMME_RUECKGABE]+linkesRandMax[TEILSUMME_RUECKGABE];
                            index_von=rechtesRandMax[INDEX_RUECKGABE];
                            index_bis=linkesRandMax[INDEX_RUECKGABE];
                        }
		}
        int[] res={teilsumme_max,index_von,index_bis};
        return res;
    }
    
    public static int maxteilsumme1(List<Integer> folge) {
            long start_zeit = System.currentTimeMillis();
            long zugriffe=0;
            int temp_Index_von=0;
            int index_von=0;
            int index_bis=0;
		int bisherMax = 0;
		int randMax = 0;
		for (int i = 0; i < folge.size(); i++) {
                        //max(0, randMax + folge[i])
                        if(randMax + folge.get(i)>0){
                            randMax=randMax + folge.get(i);
                        }else{
                            randMax=0;
                            temp_Index_von=i+1;
                        }
                        zugriffe++;
                        //max(bisherMax, randMax)
			if(randMax>bisherMax){
                            bisherMax=randMax;
                            index_von=temp_Index_von;
                            index_bis=i;
                        }
		}
                
                long end_zeit = System.currentTimeMillis();
                long laufzeit = end_zeit-start_zeit;
                System.out.println("maxteilsumme1 :");
                System.out.println("Zugriffe auf Folge:"+zugriffe);
                System.out.println("Gebrauchte Zeit in ms"+laufzeit);
                writeMessdaten(new ArrayList(Arrays.asList(new Object[]{folge.size(),"maxteilsumme1",bisherMax,index_von,index_bis,laufzeit,"N/A",zugriffe})));
		return bisherMax;
	}
}
